2400-恰好移动 k 步到达某一位置的方法数目

给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos
处。在一步移动中，你可以向左或者向右移动一个位置。

给你一个正整数 k ，返回从 startPos 出发、 恰好 移动 k 步并到达 endPos 的 不同
方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。

如果所执行移动的顺序不完全相同，则认为两种方法不同。

注意： 数轴包含负整数 。

示例 1：

**输入：** startPos = 1, endPos = 2, k = 3
**输出：** 3
**解释：** 存在 3 种从 1 到 2 且恰好移动 3 步的方法：
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
可以证明不存在其他方法，所以返回 3 。

示例 2：

**输入：** startPos = 2, endPos = 5, k = 10
**输出：** 0
**解释：** 不存在从 2 到 5 且恰好移动 10 步的方法。

提示：

• 1 <= startPos, endPos, k <= 1000

解法：数学

称 startPos 指向 endPos 的方向为正方向，startPos 远离 endPos 的方向为负方向。设从 startPos 出发，往正方向走了 a 步，往负方向走了 (k - a) 步后到达 endPos，根据组合数的定义可知答案为 C_k^a（k 步里选 a 步走正方向）。

记 d = abs(endPos - startPos)，有方程 a - (k - a) = d，得 a = d + k}{2。因此首先判断是否 (d + k) 是偶数（这样才能求出整数的 a），以及 d \le k（否则走不到），然后求组合数即可。

可以用 C_i^j = C_{i - 1}^j + C_{i - 1}^{j - 1 的递推式 \mathcal{O}(k^2) 求组合数。

参考代码（c++）

class Solution {
    const int MOD = 1000000007;

public:
    int numberOfWays(int startPos, int endPos, int K) {
        int d = abs(startPos - endPos);
        if ((d + K) % 2 == 1 || d > K) return 0;
        // 递推求组合数
        vector<vector<long long>> f;
        f.resize(K + 1, vector<long long>(K + 1));
        for (int i = 0; i <= K; i++) {
            f[i][0] = 1;
            for (int j = 1; j <= i; j++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
        }
        return f[K][(d + K) / 2];
    }
};

也可以通过 C_k^i = k - i + 1}{i}C_k^{i - 1 的递推式 \mathcal{O}(k) 求组合数，需要用到乘法逆元。

参考代码（c++）

class Solution {
    const int MOD = 1000000007;

public:
    int numberOfWays(int startPos, int endPos, int K) {
        int d = abs(startPos - endPos);
        if ((d + K) % 2 == 1 || d > K) return 0;
        // 线性求逆元
        vector<long long> inv(K + 1);
        inv[1] = 1;
        for (int i = 2; i <= K; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
        // 递推求组合数，初值 C(k, 0) = 1
        long long ans = 1;
        for (int i = 1; i <= (d + K) / 2; i++) ans = ans * (K - i + 1) % MOD * inv[i] % MOD;
        return ans;
    }
};